﻿// 检查酒驾 DRUNKEN.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://algospot.com/judge/problem/read/DRUNKEN

问题
随着假日季节的临近，由于酒后驾驶而引起的事故数量迅速增加。为了防止这种情况，首尔市宣布对酒后驾车发起战争。每天，该市会随机选择一个地点，并检查经过该地点的所有驾驶员。

在这个问题中，首尔的市中心被建模为一组V个位置和E条双向道路连接，如上图所示。每条道路都标有沿着道路行驶所需的时间。每个位置都标有在该位置进行检查时预期的延误时间。

虽然检查对每个人的安全都是好事，但这可能会导致旅行不必要的延误。现在，Hyoseung位于A位置，并且他因为与他的朋友在B位置的约会而迟到。通过找到一条拥有最小预计时间的路径来帮助他，否则他必须请客吃饭。

路径的预计时间定义如下：

[预计时间] = [沿边行驶的时间] + [检查造成的延误]
由于Hyoseung不知道检查发生在哪个位置，我们将计算假设检查是在导致最大延误的位置的情况下的最坏预计时间。

然而，我们可以假设在起始或结束位置进行的检查不会延误我们。

例如，看一下标有较粗线条的路径。沿着道路行驶需要3 + 6 + 2 = 11分钟。由于我们假设在起始和结束地点进行的检查不会影响我们，我们只考虑两个位置。由于我们不知道哪个位置将接受检查，所以我们会采取安全措施，并假设最坏情况-我们会在第一个位置接受检查，延误6分钟。因此，该路径的预计时间为17。编写一个程序来计算从A到B的最小预计时间。

输入
您的程序从标准输入中读取。输入由首尔的单个地图和T个测试案例组成。

输入的第一行是地点数V（1 <= V <= 500）和道路数E（1 <= E <= V *（V + 1）/ 2）。接下来是V个自然数的列表，列表中的第i个数字表示在该位置进行酒后驾驶检查时的延误。之后，跟随E行，每行包含三个整数A、B和C。（1 <= A,B <= V）。下一行是测试案例数T（1 <= T <= 1000）。接下来的T个测试案例将由两个整数A和B组成（1 <= A,B <= V），它们分别表示Hyoseung目前所在的地点和他的朋友等候的地点。

假设任何顶点都可以通过一条或多条道路到达其他所有顶点。给出的所有时间均不超过100。

输出
对于每个测试案例，打印一个整数，该整数是从A到B所需的最小最坏时间。

示例输入
8 12
8 6 5 8 3 5 8 4
1 6 9
1 2 3
2 8 3
6 8 5
6 7 3
8 7 3
6 5 5
4 5 7
3 4 4
3 5 2
2 3 6
7 5 1
2
1 5
6 3
示例输出
17
10
*/
int main()
{
    std::cout << "Hello World!\n";
}

 